{
 "metadata": {
  "name": "",
  "signature": "sha256:be35a4b93805aeafd2af1a2a21c219914448504672a04ef2395e8345415bc3a1"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Kernel Density Estimation"
     ]
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "by Parijat Mazumdar (GitHub ID: <a href='https://github.com/mazumdarparijat'>mazumdarparijat</a>)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This notebook is on using the Shogun Machine Learning Toolbox for [kernel density estimation](http://en.wikipedia.org/wiki/Kernel_density_estimation) (KDE). We start with a brief overview of KDE. Then we demonstrate the use of Shogun's [$KernelDensity$](http://www.shogun-toolbox.org/doc/en/latest/classshogun_1_1CKernelDensity.html) class on a toy example. Finally, we apply KDE to a real world example, thus demonstrating the its prowess as a non-parametric statistical method."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Brief overview of Kernel Density Estimation"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Kernel Density Estimation (KDE) is a non-parametric way of estimating the probability density function (pdf) of ANY distribution given a finite number of its samples. The pdf of a random variable X given finite samples ($x_i$s), as per KDE formula, is given by:\n",
      "\n",
      "$$pdf(x)=\\frac{1}{nh} \\Sigma_{i=1}^n K(\\frac{||x-x_i||}{h})$$\n",
      "\n",
      "In the above equation, K() is called the kernel - a symmetric function that integrates to 1. h is called the kernel bandwidth\n",
      "which controls how smooth (or spread-out) the kernel is. The most commonly used kernel is the normal distribution function.\n",
      "\n",
      "KDE is a computationally expensive method. Given $N_1$ query points (i.e. the points where we want to compute the pdf) and $N_2$ samples, computational complexity of KDE is $\\mathcal{O}(N_1.N_2.D)$ where D is the dimension of the data. This computational load can be reduced by spatially segregating data points using data structures like [KD-Tree](http://en.wikipedia.org/wiki/K-d_tree) and [Ball-Tree](http://en.wikipedia.org/wiki/Ball_tree). In single tree methods, only the sample points are structured in a tree whereas in dual tree methods both sample points and query points are structured in respective trees. Using these tree structures enables us to compute the density estimate for a bunch of points together at once thus reducing the number of required computations. This speed-up, however, results in reduced accuracy. Greater the speed-up, lower the accuracy. Therefore, in practice, the maximum amount of speed-up that can be afforded is usually controlled by  error tolerance values."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "KDE on toy data"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let us learn about KDE in Shogun by estimating a mixture of 2 one-dimensional gaussian distributions. \n",
      "$$pdf(x) = \\frac{1}{2} [\\mathcal{N}(\\mu_1,\\sigma_1) + \\mathcal{N}(\\mu_2,\\sigma_2)]$$\n",
      "We start by plotting the actual distribution and generating the required samples (i.e. $x_i$s)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "import scipy.stats as stats\n",
      "import matplotlib.pyplot as plt\n",
      "%matplotlib inline\n",
      "\n",
      "# generates samples from the distribution\n",
      "def generate_samples(n_samples,mu1,sigma1,mu2,sigma2):\n",
      "    samples1 = np.random.normal(mu1,sigma1,(1,n_samples/2.0))\n",
      "    samples2 = np.random.normal(mu2,sigma2,(1,n_samples/2.0))\n",
      "    samples = np.concatenate((samples1,samples2),1)\n",
      "    return samples\n",
      "\n",
      "# parameters of the distribution\n",
      "mu1=4\n",
      "sigma1=1\n",
      "mu2=8\n",
      "sigma2=2\n",
      "\n",
      "# number of samples\n",
      "n_samples = 200\n",
      "samples=generate_samples(n_samples,mu1,sigma1,mu2,sigma2)\n",
      "\n",
      "# pdf function for plotting\n",
      "x = np.linspace(0,15,500)\n",
      "y = 0.5*(stats.norm(mu1,sigma1).pdf(x)+stats.norm(mu2,sigma2).pdf(x))\n",
      "\n",
      "# plot samples\n",
      "plt.plot(samples[0,:],np.zeros(n_samples),'rx',label=\"Samples\")\n",
      "# plot actual pdf\n",
      "plt.plot(x,y,'b--',label=\"Actual pdf\")\n",
      "plt.legend(numpoints=1)\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now, we will apply KDE to estimate the actual pdf using the samples. Using KDE in Shogun is a 3 stage process : setting the model parameters, supplying sample data points for training and supplying query points for getting log of pdf estimates."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import KernelDensity, RealFeatures, K_GAUSSIAN, D_EUCLIDEAN, EM_KDTREE_SINGLE\n",
      "\n",
      "def get_kde_result(bandwidth,samples):\n",
      "    # set model parameters\n",
      "    kernel_type = K_GAUSSIAN\n",
      "    dist_metric = D_EUCLIDEAN # other choice is D_MANHATTAN\n",
      "    eval_mode = EM_KDTREE_SINGLE # other choices are EM_BALLTREE_SINGLE, EM_KDTREE_DUAL and EM_BALLTREE_DUAL\n",
      "    leaf_size = 1 # min number of samples to be present in leaves of the spatial tree\n",
      "    abs_tol = 0 # absolute tolerance\n",
      "    rel_tol = 0 # relative tolerance i.e. accepted error as fraction of true density\n",
      "    k=KernelDensity(bandwidth,kernel_type,dist_metric,eval_mode,leaf_size,abs_tol,rel_tol)\n",
      "\n",
      "    # form Shogun features and train\n",
      "    train_feats=RealFeatures(samples)\n",
      "    k.train(train_feats)\n",
      "\n",
      "    # get log density\n",
      "    query_points = np.array([np.linspace(0,15,500)])\n",
      "    query_feats = RealFeatures(query_points)\n",
      "    log_pdf = k.get_log_density(query_feats)\n",
      "    return query_points,log_pdf\n",
      "\n",
      "query_points,log_pdf=get_kde_result(0.5,samples)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We have calculated log of pdf. Let us see how accurate it is by comparing it with the actual pdf."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import matplotlib.pyplot as plt\n",
      "% matplotlib inline\n",
      "\n",
      "def plot_pdf(samples,query_points,log_pdf,title):\n",
      "    plt.plot(samples,np.zeros((1,samples.size)),'rx')\n",
      "    plt.plot(query_points[0,:],np.exp(log_pdf),'r',label=\"Estimated pdf\")\n",
      "    plt.plot(x,y,'b--',label=\"Actual pdf\")\n",
      "    plt.title(title)\n",
      "    plt.legend()\n",
      "    plt.show()\n",
      "    \n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=0.5')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We see that the estimated pdf resembles the actual pdf with reasonable accuracy. This is a small demonstration of the fact that KDE can be used to estimate any arbitrary distribution given a finite number of it's samples.  "
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Effect of bandwidth"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Kernel bandwidth is a very important controlling parameter of the kernel density estimate. We have already seen that for bandwidth of 0.5, the estimated pdf almost coincides with the actual pdf. Let us see what happens when we decrease or increase the value of the kernel bandwidth keeping number of samples constant at 200. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "query_points,log_pdf=get_kde_result(0.1,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=0.1')\n",
      "\n",
      "query_points,log_pdf=get_kde_result(0.2,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=0.2')\n",
      "\n",
      "query_points,log_pdf=get_kde_result(0.5,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=0.5')\n",
      "\n",
      "query_points,log_pdf=get_kde_result(1.1,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=1.1')\n",
      "\n",
      "query_points,log_pdf=get_kde_result(1.5,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=1.5')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "From the above plots, it can be inferred that the kernel bandwidth controls the extent of smoothness of the pdf function. Low value of bandwidth parameter causes under-smoothing (which is the case with the first 2 plots from top) and high value causes over-smoothing (as it is the case with the bottom 2 plots). The perfect value of the kernel bandwidth should be estimated using\n",
      "model-selection techniques which is presently not supported by Shogun (to be updated soon)."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Effect of number of samples"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Here, we see the effect of the number of samples on the estimated pdf, fine-tuning bandwidth in each case such that we get the most accurate pdf."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "samples=generate_samples(20,mu1,sigma1,mu2,sigma2)\n",
      "query_points,log_pdf=get_kde_result(0.7,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=20, bandwidth=0.7')\n",
      "\n",
      "samples=generate_samples(200,mu1,sigma1,mu2,sigma2)\n",
      "query_points,log_pdf=get_kde_result(0.5,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=200, bandwidth=0.5')\n",
      "\n",
      "samples=generate_samples(2000,mu1,sigma1,mu2,sigma2)\n",
      "query_points,log_pdf=get_kde_result(0.4,samples)\n",
      "plot_pdf(samples,query_points,log_pdf,'num_samples=2000, bandwidth=0.4')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Firstly, We see that the estimated pdf becomes more accurate with increasing number of samples. By running the above snippent multiple times, we also notice that the variation in the shape of estimated pdf, between 2 different runs of the above code snippet, is highest when the number of samples is 20 and lowest when the number of samples is 2000. Therefore, we can say that with increase in the number of samples, the stability of the estimated pdf increases. Both the results can be explained using the intuitive fact that a larger number of samples gives a better picture of the entire distribution. A formal proof of the same has been presented by L. Devroye in his book \"Nonparametric Density Estimation: The $L_1$ View\" [3]. It is theoretically proven that as the number of samples tends to $\\infty$, the estimated pdf converges to the real pdf."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Classification using KDE"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this section we see how KDE can be used for classification using a generative approach. Here, we try to classify the different varieties of Iris plant making use of Fisher's Iris dataset borrowed from the <a href='http://archive.ics.uci.edu/ml/datasets/Iris'>UCI Machine Learning Repository</a>. There are 3 varieties of Iris plants:\n",
      "<ul><li>Iris Sensosa</li><li>Iris Versicolour</li><li>Iris Virginica</li></ul><br>\n",
      "\n",
      "The Iris dataset enlists 4 features that can be used to segregate these varieties, but for ease of analysis and visualization, we only use two of the most important features (ie. features with very high class correlations)[refer to <a href='http://archive.ics.uci.edu/ml/machine-learning-databases/iris/iris.names'>summary statistics</a>] namely\n",
      "<ul><li>petal length</li><li>petal width</li></ul><br>\n",
      "As a first step, we plot the data."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import numpy as np\n",
      "import matplotlib.pyplot as plt\n",
      "% matplotlib inline\n",
      "\n",
      "f = open('../../../data/uci/iris/iris.data')\n",
      "features = []\n",
      "# read data from file\n",
      "for line in f:\n",
      "\twords = line.rstrip().split(',')\n",
      "\tfeatures.append([float(i) for i in words[0:4]])\n",
      "\n",
      "f.close()\n",
      "\n",
      "# create observation matrix\n",
      "obsmatrix = np.array(features).T\n",
      "\n",
      "# Just keep 2 most important features\n",
      "obsmatrix = obsmatrix[2:4,:]\n",
      "\n",
      "# plot the data\n",
      "def plot_samples(marker='o',plot_show=True):\n",
      "    # First 50 data belong to Iris Sentosa, plotted in green\n",
      "    plt.plot(obsmatrix[0,0:50], obsmatrix[1,0:50], marker, color='green', markersize=5,label='Iris Sentosa')\n",
      "    # Next 50 data belong to Iris Versicolour, plotted in red\n",
      "    plt.plot(obsmatrix[0,50:100], obsmatrix[1,50:100], marker, color='red', markersize=5,label='Iris Versicolour')\n",
      "    # Last 50 data belong to Iris Virginica, plotted in blue\n",
      "    plt.plot(obsmatrix[0,100:150], obsmatrix[1,100:150], marker, color='blue', markersize=5,label='Iris Virginica')\n",
      "\n",
      "    if plot_show:\n",
      "        plt.xlim(0,8)\n",
      "        plt.ylim(-1,3)\n",
      "        plt.title('3 varieties of Iris plants')\n",
      "        plt.xlabel('petal length')\n",
      "        plt.ylabel('petal width')\n",
      "        plt.legend(numpoints=1,bbox_to_anchor=(0.97,0.35))\n",
      "        plt.show()\n",
      "    \n",
      "plot_samples()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next, let us use the samples to estimate the probability density functions of each category of plant."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from modshogun import KernelDensity, RealFeatures, K_GAUSSIAN, D_EUCLIDEAN, EM_BALLTREE_DUAL\n",
      "import scipy.interpolate as interpolate\n",
      "\n",
      "def get_kde(samples):\n",
      "    # set model parameters\n",
      "    bandwidth = 0.4\n",
      "    kernel_type = K_GAUSSIAN\n",
      "    dist_metric = D_EUCLIDEAN\n",
      "    eval_mode = EM_BALLTREE_DUAL\n",
      "    leaf_size = 1\n",
      "    abs_tol = 0\n",
      "    rel_tol = 0\n",
      "    k=KernelDensity(bandwidth,kernel_type,dist_metric,eval_mode,leaf_size,abs_tol,rel_tol)\n",
      "    \n",
      "    # form Shogun features and train\n",
      "    train_feats=RealFeatures(samples)\n",
      "    k.train(train_feats)\n",
      "    \n",
      "    return k\n",
      "\n",
      "def density_estimate_grid(kdestimator):\n",
      "    xmin,xmax,ymin,ymax=[0,8,-1,3]\n",
      "\n",
      "    # Set up a regular grid of interpolation points\n",
      "    x, y = np.linspace(xmin, xmax, 100), np.linspace(ymin, ymax, 100)\n",
      "    x, y = np.meshgrid(x, y)\n",
      "\n",
      "    # compute density estimate at each of the grid points\n",
      "    query_feats=RealFeatures(np.array([x[0,:],y[0,:]]))\n",
      "    z=np.array([kdestimator.get_log_density(query_feats)])\n",
      "    z=np.exp(z)\n",
      "    for i in xrange(1,x.shape[0]):\n",
      "        query_feats=RealFeatures(np.array([x[i,:],y[i,:]]))\n",
      "        zi=np.exp(kdestimator.get_log_density(query_feats))\n",
      "        z=np.vstack((z,zi))\n",
      "\n",
      "    return (x,y,z)\n",
      "\n",
      "def plot_pdf(kdestimator,title):\n",
      "\n",
      "    # compute interpolation points and corresponding kde values\n",
      "    x,y,z=density_estimate_grid(kdestimator)\n",
      "    \n",
      "    # plot pdf\n",
      "    plt.imshow(z, vmin=z.min(), vmax=z.max(), origin='lower',extent=[x.min(), x.max(), y.min(), y.max()])\n",
      "    plt.title(title)\n",
      "    plt.colorbar(shrink=0.5)\n",
      "    plt.xlabel('petal length')\n",
      "    plt.ylabel('petal width')\n",
      "    plt.show()\n",
      "\n",
      "    \n",
      "kde1=get_kde(obsmatrix[:,0:50])\n",
      "plot_pdf(kde1,'pdf for Iris Sentosa')\n",
      "\n",
      "kde2=get_kde(obsmatrix[:,50:100])\n",
      "plot_pdf(kde2,'pdf for Iris Versicolour')\n",
      "\n",
      "kde3=get_kde(obsmatrix[:,100:150])\n",
      "plot_pdf(kde3,'pdf for Iris Virginica')\n",
      "\n",
      "kde=get_kde(obsmatrix[:,0:150])\n",
      "plot_pdf(kde,'Combined pdf')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The above contour plots depict the pdf of respective categories of iris plant. These probability density functions can be used\n",
      "as generative models to estimate the likelihood of any test sample belonging to a particular category. We use these likelihoods for classification by forming a simple decision rule: a test sample is assigned the class for which it's likelihood is maximum. With this in mind, let us try to segregate the \n",
      "entire 2-D space into 3 regions :\n",
      "<ul><li>Iris Sentosa (green)</li><li>Iris Versicolour (red)</li><li>Iris Virginica (blue)</li></ul>"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# get 3 likelihoods for each test point in grid\n",
      "x,y,z1=density_estimate_grid(kde1)\n",
      "x,y,z2=density_estimate_grid(kde2)\n",
      "x,y,z3=density_estimate_grid(kde3)\n",
      "\n",
      "# classify using our decision rule\n",
      "z=[]\n",
      "for i in xrange(0,x.shape[0]):\n",
      "    zj=[]\n",
      "    for j in xrange(0,x.shape[1]):\n",
      "        if ((z1[i,j]>z2[i,j]) and (z1[i,j]>z3[i,j])):\n",
      "            zj.append(1)\n",
      "        elif (z2[i,j]>z3[i,j]):\n",
      "            zj.append(2)\n",
      "        else:\n",
      "            zj.append(0)\n",
      "            \n",
      "    z.append(zj)\n",
      "\n",
      "z=np.array(z)\n",
      "\n",
      "# plot results\n",
      "plt.imshow(z, vmin=z.min(), vmax=z.max(), origin='lower',extent=[x.min(), x.max(), y.min(), y.max()])\n",
      "plt.title(\"Classified regions\")\n",
      "plt.xlabel('petal length')\n",
      "plt.ylabel('petal width')\n",
      "plot_samples(marker='x',plot_show=False)\n",
      "plt.show()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The classified regions that we get almost match our intuitive expectation. In the plot, the exact position of the 2 decision boundaries can be controlled by varying the kernel bandwidth parameter."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "References"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "[1] Bache, K. & Lichman, M. (2013). UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA: University of California, School of Information and Computer Science\n",
      "\n",
      "[2] Wikipedia page on Kernel Density Estimation. http://en.wikipedia.org/wiki/Kernel_density_estimation\n",
      "\n",
      "[3] L. Devroye and L. Gyorfi.Nonparametric Density Estimation: The $L_1$ View. Wiley, 1985"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}